package com.ding.practice.algorithm.leetcode.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 力扣热题100之合并区间
 * @ID = 56
 * @date 2024年07月18日15:54:51
 *
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2：
 *
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 *
 *
 * 提示：
 *
 * 1 <= intervals.length <= 104
 * intervals[i].length == 2
 * 0 <= starti <= endi <= 104
 */
public class Merge_56 {

    /*
    核心思想就是，创建一个新的返回数组，将遍历到的数组和返回数组的最后一个做比较，看是否合并，是否跳过
     */
    public static int[][] merge(int[][] intervals) {
        // 先进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];

            }
        });
        List<int[]> retList = new ArrayList<>();
        // 将数组的第一个添加到需要返回的数组中
        retList.add(new int[]{intervals[0][0], intervals[0][1]});
        if (intervals.length == 1){
            return intervals;
        }
        int index = 0;
        // 遍历数组，将遍历到的数组和已经加到返回数组的最后一个进行比较
        for (int i = 1; i < intervals.length; i++){
            // 当前的数组左边大于上一个数组的右边，不包含，直接加到返回的数组中
            if (retList.get(index)[1] < intervals[i][0]){
                retList.add(new int[]{intervals[i][0], intervals[i][1]});
                index ++;
                continue;
            }
            // 当数组交叉时，即返回数组的右边大于当前数组的左边，并且返回数组的右边小于当前数组的右边
            if (retList.get(index)[1] >= intervals[i][0] && retList.get(index)[1] <= intervals[i][1]){
                // 合并,以上一个的左边和这一个的右边为新区间
                int [] temp = new int[]{retList.get(index)[0], intervals[i][1]};
                // 需要移除旧的，把新数组添加进去
                retList.remove(index);
                retList.add(temp);
            }
        }
        return retList.toArray(new int[retList.size()][]);
    }


    /*
    先进性以左边端点进行排序，后逐个进行比较，是否需要合并，后更新到一个新数组里，不过这个方法申请的内存有点多，需要优化一下
     */
    public static int[][] merge2(int[][] intervals) {
        // 先进行排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
               return o1[0] - o2[0];

            }
        });
        List<List<Integer>> retList = new ArrayList<>();
        List<Integer> tempList = new ArrayList<>();
        tempList.add(intervals[0][0]);
        tempList.add(intervals[0][1]);
        retList.add(tempList);
        if (intervals.length == 1){
            return intervals;
        }
        int index = 0;
        for (int i = 1; i < intervals.length; i++){
            if (retList.get(index).get(1) < intervals[i][0]){
                List<Integer> tempList2 = new ArrayList<>();
                tempList2.clear();
                tempList2.add(intervals[i][0]);
                tempList2.add(intervals[i][1]);
                retList.add(tempList2);
                index ++;
                continue;
            }
            if (retList.get(index).get(1) >= intervals[i][0] && retList.get(index).get(1) <= intervals[i][1]){
                // 合并,以上一个的左边和这一个的右边为新区间
                List<Integer> tempList3 = new ArrayList<>();
                tempList3.clear();
                tempList3.add(retList.get(index).get(0));
                tempList3.add(intervals[i][1]);
                retList.remove(index);
                retList.add(tempList3);
            }else {
                // 合并,已上一个为区间

            }
        }
        int[][] retArray = convert(retList);
        return retArray;
    }
    public static int[][] convert(List<List<Integer>> list) {
        int[][] array = new int[list.size()][];
        for (int i = 0; i < list.size(); i++) {
            List<Integer> innerList = list.get(i);
            array[i] = new int[innerList.size()];
            for (int j = 0; j < innerList.size(); j++) {
                array[i][j] = innerList.get(j);
            }
        }
        return array;
    }
    public static void main(String[] args) {
        int[][] intervals = {{1,4},{0,2},{3,5}};
        System.out.println(merge(intervals));
    }
}
